//************************************************************
//    > File Name: sqrt.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月27日 10:27:31
//***********************************************************
//lintcode #141
#include<bits/stdc++.h>
using namespace std;
int sqrt1(int x){
	if(x==1) return 1;
	int left =0;
	int right=x / 2 +1;
	while(right - left >1){
		int mid = left +(right - left)/2;
		if(mid > x / mid) right = mid;
		else if(mid < x/mid) left = mid;
		else return mid;
	}
	return right-1;
}
int sqrt2(int x){
	if(x==1) return 1;
	int left=1;
	int right=x/2+1;
	while(left<right){
		int mid = left + (right-left)/2;
		if(mid>x/mid) right=mid;
		else left=mid+1;
	}
	return left-1;
}
int main(){
	int x;
	cout<<"please enter a number :";
	cin>>x;
	cout<<"sqrt(x) is "<<sqrt1(x)<<endl;
}
